%\documentclass[runningheads,a4paper]{article}
%\documentclass[a4paper,10pt,draft]{article}
%\documentclass[runningheads,a4paper,10pt]{article}
\documentclass[a4paper,10pt]{article}

\usepackage{amsmath}    
\usepackage{amsfonts}
\usepackage{amssymb}

\usepackage{graphicx}

% Paquetes para el idioma, las tildes, etc.
\usepackage[activeacute,spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fontenc}
\usepackage{textcomp}

\usepackage[numbers,sort&compress]{natbib}
\usepackage{url}
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}

\bibliographystyle{unsrtnat}

\begin{document}

%\mainmatter 

\title{Interacción con entornos dinámicos usando automatas celulares}

%\titlerunning{Interacción con entornos dinámicos usando automatas celulares}


\author{Ramiro Castro\\
\small{Fa.M.A.F.,Universidad Nacional de Córdoba, Argentina}\\
\small{\url{http://www.famaf.unc.edu.ar}}\\
\small{\texttt{castro.ramiro@gmail.com}}
\and
Juan Pablo Carbajal\\
\small{Laboratorio de Inteligencia Artificial, Universidad de Z\"{u}rich, Suiza}\\
\small{\url{http://ailab.ch}}\\
\small{\texttt{carbajal@ifi.uzh.ch}}
}

\maketitle


\begin{abstract}
En el presente trabajo describimos un ejemplo de aplicación de autómatas celulares para la simulación de entornos dinámicos en videojuegos con múltiples agentes autónomos. Los autómatas celulares (CA) han sido considerados para la implentación de fenómenos físicos como la propagación de fuego, olas en superficies de fluídos, ondas de presión, o difusión de ga\-ses; sin embargo su uso en videojuegos no es frecuente. Aquí reportamos brevemente la integración de estas herramientas en sistemas con múltiples agentes, discutimos sus ventajas y desventajas y proveemos algunos ejemplos.

\textbf{Keywords:}cellular automata, swarm intelligence, dynamic environments, characters movement, video games.
\end{abstract}


\section{Introducción}

En el presente trabajo se muestra una opción de implementación de \textit{entornos dinámicos} usando \textit{autómatas celulares (CA)} junto con algoritmos de \textit{flocking} para el movimiento de grupos de agentes. Los videojuegos de hoy presentan detalles gráficos sin precendentes. Sin embargo la inmersión y la jugabilidad siguen obstaculizados por la simplicidad de los escenarios y la inteligencia de los agentes. Esta última puede encontrar soluciones en la AI \cite{cog-mod-games,Ram_twentiethinternational,ai-for-comp-games,ai-stim-response,ai-madness} mientras que la primera pueden encontrarla en los CA, aunque con un coste más notable en la performance. Aquí nos concentramos en el acople de ambas soluciones.

Los agentes se animan aplicando técnicas de flocking\cite{Reynolds99steeringbehaviors,modeling-fish} basadas en las reglas de Craig Reynolds\cite{Reynolds87}\footnote{Texto y material disponible en \url{http://www.red3d.com/cwr/}}: \textit{separación, alineación y cohesión}. Estas reglas son todas locales y se aplican a cada agente del sistema. El movimiento colectivo observado es un fenómeno emergente, sin necesidad de comportamientos pre-programados estrictos. Las reglas pueden modificarse según lo que se desee simular e incluso se pueden agregar reglas como: alejarse de predadores, busqueda de calor, comida, etc.

Los entornos dinámicos son escenarios del videojuego cuyo estado varía si\-guien\-do reglas de evolución y pueden ser simulados utilizando un CA. El uso de CA para la simulación de entornos dinámicos ha demostrado alcanzar un alto nivel de realismo \cite{cgarcia-lattice} y la implementación de algoritmos no agrega complejidad al desarrollo del juego \cite{ca-modeling}. Basta definir la forma de actualización del CA que lo simulará y sus estados. 

Lo que se espera lograr combinando estas técnicas, flocking y CA, es que los agentes puedan interactuar libremente con el entorno dinámico y que ambos reaccionen de forma natural y flexible. 

\section{Ejemplo de aplicaci\'on}
Para motivar al lector comenzamos nuestra exposici\'on con un ejemplo de aplicaci\'on del sistema propuesto. En la Figura \ref{fig:EjemploX} se muestran capturas de pantallas de un simple simulador programado en Python usando pygame. Los cuadrados rojos representan agentes moviéndose en rebaño que se ven afectados por explosiones en el entorno. Estas explosiones afectan a los agentes impulsándolos con una fuerza que depende de la diferencia de presión y es en el sentido que se expande la onda, como se explica en la sección \ref{sec:Acop}.

\begin{figure}[htb]
\centering
\includegraphics[width=.7\textwidth]{./img/Castro_Carbajal_Fig1.eps}
\caption{\label{fig:EjemploX} Agentes(cuadrados en rojo) siendo afectados por explosiones y una pared (línea en rojo) que contienen las explosiones. Fig. a)Agentes moviéndose en manada libremente mientras ocurre una explosión detrás de la pared. Fig. b) Las explosiones rodean la pared pero aún no afectan a los agentes. Fig. c) y d) dos explosiones continuas, la primera apenas afecta a los agentes mientras que la segunda los empuja hacia la derecha de la pantalla. En Fig. f) y g) se ve la propagación de las explosiones anteriores y como éstas separan a los agentes.}
\end{figure}


\section{Descripción del autómata}
El CA consiste en una matriz de celdas (grilla) y cada celda tiene cuatro vecinos: arriba, abajo, izquierda y derecha. Cada celda es capaz de contener una magnitud real que, en este caso, representa la presión de un fluido. Una perturbación en el valor de la presión en un punto se propaga a toda la grilla por medio de reglas de actualización que definen la evolución del CA. En la Figura \ref{fig:EjemploX} se puede observar la propagación de varias singularidades generadas en la grilla, representando explosiones.

Las reglas utilizadas se describen en detalle en una publicación de Tom Forsyth\cite{ca-modeling} que se destaca por su claridad y se sugiere al lector revisar dicha publicación para los detalles técnicos. Forsyth mantiene una página web\footnote{\url{http://home.comcast.net/~tom_forsyth/}} donde el contenido de \cite{ca-modeling} est\'a parcialmente reproducido. En la Figura \ref{fig:CA} mostramos la representación de objetos estáticos en el espacio del juego (considerado {\it con\-ti\-nuo}), en el espacio discreto defindo por la grilla del CA. En la figura, las celdas oscuras no son actualizadas por el CA (celdas inertes)y por lo tanto la presión no se propaga a través de ellas. Las celdas que representan al objeto se seleccionan utilizando el bounding box de cada objeto (la caja de menor área que encierra completamente la base del objeto), es decir, todas las celdas contenindas en el bouding box son consideradas inertes.

\begin{figure}[htb]
\centering
\includegraphics[width=.7\textwidth]{./img/Castro_Carbajal_Fig2.eps}
\caption{\label{fig:CA} Representación de objetos estáticos en el CA. Los objetos en el espacio {\it continuo} se proyectan sobre las celdas del CA. Estas celdas aceptan propiedades de {\it porosidad} que regulan el flujo de material o simplemente no se actualizan, representando objetos sólidos. La sequencia muestra la evolución de una explosión iniciada fuera de un recinto.}
\end{figure}

\section{\label{sec:Acop} Acoplamiento con agentes}
Los agentes se mueven en el espacio continuo. La actualización de sus posiciones puede hacerse en base a velocidad y fuerza o en base a su posición. Si se basa en velocidades y aceleraciones es necesario implementar un integrador, o en otras palabras, necesitamos un motor de física. En la actualidad existen bibliotecas de acceso libre de muy buena calidad: 2D, rescatamos Chipmunk\cite{chip}, por su simplicidad y facilidad de programación; en 3D, los motores suelen ser más complicados y el emblema de la comunidad libre de hoy es Bullet Physics\cite{bullet}. Es posible prescindir de integradores basados en velocidad e implementar la física utilizando únicamente las posiciones de los agentes\cite{Muller2007109}. Sin embargo, no tenemos experiencia con estos motores. En este trabajo se eligió utilizar movimientos basados en fuerzas. Est\'a elección facilita el acoplamiento de los agentes con el CA subyacente. Al igual que los objetos estáticos, los agentes son representados en el espacio discreto utilizando la proyección de su bounding box. La fuerza sobre el agente, causada por las ondas de presión fluyendo en el CA, se calcula en base a las diferencias de presión sobre los lados del agente, como se muestra en la Figura \ref{fig:Coupling}. Es decir, la componente horizontal de la fuerza está dada por la diferencia entre la presión en los lados izquierdo y derecho. La componente vertical por la diferencia entre las celdas superiores e inferiores. En ecuaciones podemos escribir,

\begin{eqnarray}
p_j &=& \sum_i \vert p_{ij} \vert \quad j=\mathsf{u,d,l,r} \\
\label{eq:dP}\vec{F} &=& \left( p_u - p_d, p_l -p_r \right).
\end{eqnarray}

\begin{figure}[htb]
\centering
\includegraphics[width=.8\textwidth]{./img/Castro_Carbajal_Fig3.eps}
\caption{\label{fig:Coupling} Acoplamiento del CA con los agentes. Las celdas del CA totalmente incluídas en el bounding box del agente se utilizan para calcular la fuerza. Las componentes vertical y horizontal se calculan haciendo la diferencia entre las celdas superiores e inferiores y entre las celdas a la izquierda y a la derecha, respectivamente.}
\end{figure}

\noindent Donde $\mathsf{u,d,l,r}$ indican arriba, abajo, izquierda y derecha, respectivamente. La presión en cada celda se denomina $p_{ij}$, donde el subíndice $i$ recorre las celdas del lado correspondiente. Tomamos el valor abosluto, dado que los valores de $p_{ij}$ pueden ser negativos, de esta manera la suma refleja la "activitad" del CA. Si se omite, el efecto de la presión sobre el agente es menor. El signo de las diferencias en la ecuación (\ref{eq:dP}) depende de las convenciones utilizadas y pueden variar seg\'un la implementaci\'on.


\section{Discusión y conclusión}

Los CA presentados aquí han sido utilizados en el pasado en proyectos comerciales tales como X-Com\cite{xcom} y Silent Storm\cite{silentstorm} y otros juegos en base a turnos en donde el desempeño numérico de los algoritmos no es crítico. En contraste, hemos presentado un esquema de acoplamiento de CA con agentes que se mueven a tiempo real y donde algoritmos eficientes de actualización son estrictamente necesarios. Al tiempo de esta publicación nuestro CA se actualiza de manera no optimizada, especialmente notorio cuando el fenómeno natural que deseamos simular se propaga muy rápidamente, como las explosiones; en\cite{ca-modeling} se brindan soluciones usando octrees o quadtrees. Sin embargo nuestro aporte a la publicación de Tom Forsyth\cite{ca-modeling} radica en el acople con agentes y técnicas de flocking. Variaciones al esquema pueden encontrarse en los trabajos de C.G. Bauza\cite{cgarcia-lattice} que han demostrado ser altamente eficientes. Existen otras técnicas empleadas para el simulado de explosiones en videojuegos, entre ellas los {\it sistemas de partículas} \footnote{Artículo online describiendo el algoritmo básico  \url{http://www.gamasutra.com/view/feature/2122/building_a_millionparticle_system.php}}, que han alcanzado un alto nivel de desarrollo.

Con respecto a la performance se hicieron pruebas de ejecucion con y sin explosiones de 500 iteraciones cada una en su bucle de actualización principal. Se determinó que si ocurren muchas explosiones entonces el tiempo de ejecución puede subir a más del 350\%, siendo que el 75\% de este tiempo es consumido por las funciones que propagan las explosiones. Es por esto que hacemos la mención de la performance en la actualización del CA.

La topología de grilla utilizada en nuestra aplicación no es necesaria. El automata celular puede implementarse sobre un grafo arbitrario. Esto brinda flexibilidad al modelado del escenario. Trabajos en esta dirección son llevados a cabo en academia, sin embargo la transferencia al mercado de los videojuegos es alarmantemente lenta.

Cabe señalar que en videojuegos, la precisión de las simulaciones de fenómenos físicos no es una necesidad, simplemente necesitamos captuar el comportamiento cualitativo del fen\'omeno. Este hecho pareciera indicar que una base en física o control (para los comportamientos de los agentes) no son requerimientos. Sin embargo, solo el concimiento adecuado de técnicas en dichas disciplinas permite desarrollar simplificaciones efectivas y útiles para videojuegos, y a la vez acelera la transferencia de desarrollos.

También creemos que una aplicación concreta sería un juego donde se necesita mover o dirigir agentes y objetos mediante ondas de presión. 

\section*{Agradecimientos}
Agradecemos a Ezequiel Pozzo por incontables discusiones técnicas. Agradecemos a la comisión organizadora por sus esfuerzos y su apoyo. También queremos agradecer a varios artistas por liberar los derechos de todas sus obras (utilizadas en este manuscrito) y permitir el uso libre y gratuito de ellas. Agradecemos los comentarios y correcciones brindadas por los correctores.

\small{\bibliography{../referencias}}

\end{document}
